use std::collections::HashSet;
use regex::Regex;

type Coord = (i64, i64);

fn parse_input() -> Vec<((Coord, i64), Coord)> {
    let re = Regex::new(r"[0-9]+").unwrap();
    include_str!("../input.txt")
        .lines()
        .map(|line| -> ((Coord, i64), Coord) {
            let mut numbers: Vec<i64> = Vec::new();
            for (res, []) in re.captures_iter(line).map(|c| c.extract()) {
                numbers.push(res.parse().unwrap());
            }

            let sx = numbers[0];
            let sy = numbers[1];
            let bx = numbers[2];
            let by = numbers[3];

            let radius = (sx - bx).abs() + (sy - by).abs();

            (((sx, sy), radius), (bx, by))
        })
        .collect()
}

fn part1() {

    const ROW: i64 = 2000000;

    let sbs = parse_input();

    let beacon_xs = sbs
        .iter()
        .map(|t| t.1)
        .filter(|c| c.1 == ROW)
        .map(|c| c.0)
        .collect::<HashSet<i64>>();

    let mut x_set = HashSet::new();
    for ((sensor, radius), _) in sbs {
        let distance = radius - (sensor.1 - ROW).abs();
        if distance >= 0 {
            for i in 0..distance + 1 {
                let x = sensor.0 + i;
                if !x_set.contains(&x) && !beacon_xs.contains(&x) {
                    x_set.insert(x);
                }

                let x = sensor.0 - i;
                if !x_set.contains(&x) && !beacon_xs.contains(&x) {
                    x_set.insert(x);
                }
            }
        }
    }

    println!("Part 1: {}", x_set.len());
}

fn part2() {
    const LIMIT: i64 = 4000000;
    let sensors: Vec<_> = parse_input().into_iter().map(|t| t.0).collect();

    for y in 0..=LIMIT {
        let mut x = 0;
        let mut changed = true;
        while changed {
            changed = false;
            for &((sx, sy), radius) in sensors.iter() {
                let distance = (sx - x).abs() + (sy - y).abs();
                if distance <= radius {
                    x = sx + radius - (sy - y).abs() + 1;
                    changed = true;
                }
            }
        }
        if x <= LIMIT {
            println!("Part 2: {}", LIMIT * x + y);
            return;
        }
    }
}

fn main() {
    part1();
    part2();
}